package code.c04_String.homework;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/20 22:59
 * @package code.c04_String.homework
 * @description HDU2087—剪花布条问题
 * 时间限制：10000ms，空间限制：32768K。
 * 问题描述：一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
 * 输入格式：输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。
 * 输出格式：输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。
 *
 * 输入示例：
 * abcde a3
 * aaaaaa  aa
 * #
 *
 * 输出示例：
 * 0
 * 3
 */

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String scannerStr = scanner.nextLine();
        ArrayList<Integer> arrayList = new ArrayList<>();

        while (!scannerStr.equals("#")){
            // 切割字符串
            String[] tmps = scannerStr.split(" ");
            String str = tmps[0];
            String sub = tmps[1];

            int count = 0;

            // 找到子串并截取掉
            while (KMP(str, sub, 0) != -1){
                count += 1;
                int kmp = KMP(str, sub, 0);

                // 截取字符串
                str = str.substring(kmp + sub.length());
            }

            arrayList.add(count);
            scannerStr = scanner.nextLine();
        }

        for (Integer a:arrayList) {
            System.out.println(a);
        }

    }

    public static int KMP(String str, String sub, int pos) {
        // 非法约束
        if (str == null || sub == null) {
            return -1;
        }

        if (str.length() == 0 || sub.length() == 0) {
            return -1;

        }

        if (pos < 0 || pos >= str.length()) {
            return -1;
        }

        int i = pos; // 主串
        int j = 0; // 子串

        int[] next = new int[sub.length()];

        // 获取 next 数组
        getNext(sub, next);

        // 遍历主串 和 子串
        while (i < str.length() && j < sub.length()) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j >= sub.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    private static void getNext(String sub, int[] next) {
        next[0] = -1;
        next[1] = 0;

        int i = 2;
        int k = 0;

        for (; i < sub.length(); i++) {
            if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)) {
                next[i] = k + 1;
                k++;
                i++;
            } else {
                k = next[k];
            }
        }
    }
}


